To facilitate the utilization of data center resources, virtualization technologies may allow a single physical computing machine to host one or more instances of virtual machines that appear and operate as independent computer machines to a connected computer user. With virtualization, the single physical computing device can create, maintain, or delete virtual machines in a dynamic manner. In a large distributed computing system (e.g., multiple distributed data centers) of a computing resource service provider, various customers, users, services, and resources of the computing resource service provider are frequently shared between customers. In addition, these computing resources are often leveraged in large-scale networks of computers, servers, and storage drives to enable clients, including content providers, online retailers, customers and the like, to host and execute a variety of applications and web services.
The usage of network computing allows content providers and customers, among others, to efficiently and adaptively satisfy their computing needs. However, with the growing use of virtual resources, customers are encountering situations in which networking these virtual resources becomes difficult and does not scale well. In addition, customers may operate these virtual resources within virtual private networks secure from other computing resources outside of these virtual private networks. However connecting these virtual private networks so that virtual resources or other computing resources within these virtual private networks can communicate also becomes increasingly difficult as the size, complexity, and number of these virtual private networks increases. Many technologies such as Border Gateway Protocol (BGP) do not provide a mechanism for effectively scaling either in the amount of routing information or the number of these virtual private networks that are interconnected.